﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace eu.h8me.Parsing.LexerLib2 {

    /// <summary>
    /// Helper class for creating and storing a deterministic finite automaton for a TNFA.
    /// </summary>
    internal class TDFA {

        // Constants.
        private const int START_STATE = 0;

        // Data.
        private List<ITNFATag> _Initializers;
        private Dictionary<int, List<TDFATransition>> _States = new Dictionary<int, List<TDFATransition>>();
        private Dictionary<int, List<TDFAMatch>> _Matchers = new Dictionary<int, List<TDFAMatch>>();

        /// <summary>
        /// Initialize a new TDFA implementing matching the set of passed regular expressions (with parsed TNFA automatons).
        /// </summary>
        /// <param name="nfas">RegEx instances to combine into this TDFA.</param>
        public TDFA(IEnumerable<RegEx> regex) {
            // Initialize new TNFA state which dispatches to passed TNFAs.
            TNFAState start = new TNFAState();
            Dictionary<TNFAState, RegEx> match = new Dictionary<TNFAState, RegEx>();

            // Loop over all passed TNFAs, adapting them for the current state and attaching them.
            foreach( RegEx re in regex ) {
                // Clone the TNFA for attaching it to base and attach it from start. Record the matching TNFA in match set.
                TNFA clone = re.Automaton.Clone(null);
                start.EpsilonTransitions.Add(new TNFAEpsilonTransition(clone.Begin));
                match[clone.End] = re;
            }

            // Initialize starting TNFA state set and store initializers for it.
            TNFAStateSet begin = new TNFAStateSet(start);
            _Initializers = new List<ITNFATag>(begin.CreateTagIndex.Keys);

            // Initialize states dictionary and processing count.
            Dictionary<TNFAStateSet, int> states = new Dictionary<TNFAStateSet, int>();
            int laststate = START_STATE;
            states[begin] = laststate;

            // Initialize state processing stack and add beginning object.
            Stack<object> toprocess = new Stack<object>();
            toprocess.Push(begin);
            toprocess.Push(laststate);
            while( toprocess.Count > 0 ) {
                // Fetch state and ID and initialize state set.
                int stateid = (int)toprocess.Pop();
                TNFAStateSet state = (TNFAStateSet)toprocess.Pop();
                _States[stateid] = new List<TDFATransition>();

                // Walk transitions from this state set to reach new states.
                foreach( TNFASetTransition trans in state.Reach() ) {
                    // Check whether target state is known. If not, enter it.
                    int targetid;
                    if( !states.TryGetValue(trans, out targetid) ) {
                        // No, need to enter it.
                        states[trans] = targetid = ++laststate;
                        toprocess.Push(trans);
                        toprocess.Push(targetid);
                    }

                    // Record transition to target, with the respective adaptations.
                    _States[stateid].Add(new TDFATransition(trans.Range, trans.AdaptTagIndex, trans.CreateTagIndex, targetid));
                }

                // Process matches in this state set.
                foreach( TNFAStateDescription desc in state.States ) {
                    // Check whether this matches a regex.
                    RegEx matcher;
                    if( !match.TryGetValue(desc.State, out matcher) )
                        continue;

                    // Found a match, fetch list to record it.
                    List<TDFAMatch> matches;
                    if( !_Matchers.TryGetValue(stateid, out matches) )
                        _Matchers[stateid] = matches = new List<TDFAMatch>();

                    // Record the match with the indices of the tags to use for match.
                    matches.Add(new TDFAMatch(matcher, desc.Tags));
                }
            }
        }

        /// <summary>
        /// Fetch initializer list of this TDFA.
        /// </summary>
        public IEnumerable<ITNFATag> Initializers {
            get {
                // Return list of initializers for this TDFA.
                return _Initializers;
            }
        }

        /// <summary>
        /// Fetch state set for this TDFA.
        /// </summary>
        public Dictionary<int, List<TDFATransition>> States {
            get {
                // Return state set.
                return _States;
            }
        }

        /// <summary>
        /// Fetch the matcher set of this TDFA.
        /// </summary>
        public Dictionary<int, List<TDFAMatch>> Matchers {
            get {
                // Fetch matcher set for this TDFA.
                return _Matchers;
            }
        }

    }

    /// <summary>
    /// Helper class to record a TDFA transition and the relevant operations to perform.
    /// </summary>
    internal class TDFATransition {

        // Data.
        private Range _Range;
        private SortedDictionary<ITNFATag, SortedDictionary<int, int>> _AdaptTagIndex;
        private SortedDictionary<ITNFATag, int> _CreateTagIndex;
        private int _Target;

        /// <summary>
        /// Initialize a new TDFA transition which matches on the specified character range, performs the noted adjustments to
        /// tag(s), and finishes in the destination state.
        /// </summary>
        /// <param name="range">Character range to perform transition on.</param>
        /// <param name="adapt">Adaptation to tags for indexes.</param>
        /// <param name="create">Creation of new tags for indexes.</param>
        /// <param name="target">Target TDFA state to move to.</param>
        public TDFATransition(Range range, SortedDictionary<ITNFATag, SortedDictionary<int, int>> adapt, SortedDictionary<ITNFATag, int> create, int target) {
            // Store data.
            _Range = range;
            _AdaptTagIndex = adapt;
            _CreateTagIndex = create;
            _Target = target;
        }

        /// <summary>
        /// Fetch lower bound of character range which takes this transition.
        /// </summary>
        public char Start {
            get {
                // Return start char.
                return _Range.Start;
            }
        }

        /// <summary>
        /// Fetch upper bound of character range which takes this transition.
        /// </summary>
        public char Stop {
            get {
                // Return stop char.
                return _Range.Stop;
            }
        }

        /// <summary>
        /// Fetch tag adaptations for this transition.
        /// </summary>
        public SortedDictionary<ITNFATag, SortedDictionary<int, int>> AdaptTagIndex {
            get {
                // Return adaptations.
                return _AdaptTagIndex;
            }
        }

        /// <summary>
        /// Fetch tag creations for this transition.
        /// </summary>
        public SortedDictionary<ITNFATag, int> CreateTagIndex {
            get {
                // Return tag creations for this index.
                return _CreateTagIndex;
            }
        }

        /// <summary>
        /// Fetch target state to move to after this transition.
        /// </summary>
        public int Target {
            get {
                // Return target state.
                return _Target;
            }
        }

    }

    /// <summary>
    /// Helper class used to store a match possibility in a TDFA state.
    /// </summary>
    internal class TDFAMatch {

        // Data.
        private RegEx _RegEx;
        private SortedDictionary<ITNFATag, int> _Tags;

        /// <summary>
        /// Initialize a new TDFA match helper, which is bound to the specified regex, which receives the listed tags on match.
        /// </summary>
        /// <param name="regex">Regular expression that matched.</param>
        /// <param name="tags">Tag positions to deliver to match.</param>
        public TDFAMatch(RegEx regex, SortedDictionary<ITNFATag, int> tags) {
            // Store data.
            _RegEx = regex;
            _Tags = tags;
        }

        /// <summary>
        /// Fetch regex that matches when this state is up.
        /// </summary>
        public RegEx RegEx {
            get {
                // Return matching regex.
                return _RegEx;
            }
        }

        /// <summary>
        /// Fetch tag set in matching regex.
        /// </summary>
        public SortedDictionary<ITNFATag, int> Tags {
            get {
                // Return tag set.
                return _Tags;
            }
        }

    }

}
